数据链路层 Data Link Layer

成帧 Framing

成帧 Framing 的核心任务是设计一种方案使得接收方很容易找到每个帧的开始，从而将比特流还原成一个个帧；同时不能占用太多带宽。

• 字节计数法（byte count）：这种方式在每个 frame 的开头用一个 byte 保存这个 frame 的 byte 数目。但是当这个计数值出现错误时，即使接收方通过错误检验发现了错误，也再也无法知道下一帧的开始位置（失去同步 get out of sync）。
• 标志计数法（Flag bytes）
  • 
  • 使用特殊字符 FLAG 标志帧的开始与结束，同时使用转义字符做区分
  • 由于以字节为单位，发送的开销较大
• 标志比特法（Flag bits）
  • 考虑到帧的划分也可以是比特级的，这种标志和填充也可以精确到比特级。例如 HDLC 的标志方式是：每个帧的开始和结束用序列 01111110 (0x7E) 标识，同时发送方的数据链路层在数据中每发现连续的 5 个 1，发送时就在其后面添加一个 0；接收方的数据链路层在发现 111110 时将最后一个 0 舍弃。这种技术称为 比特填充 bit stuffing。
• 物理层编码违禁法（Physical layer coding violations）
  • 对于 4B/5B 编码方式或者 Manchester 编码，有相当一部分信号组合是不可能出现的。我们可以使用这样的信号组合作为帧的开始和结束。相对于上面两种填充方法，这种方法不再需要填充数据。IEEE 802 标准就采用了这种方法。

检错与纠错 Error Control

• 码字（codeword）：n(码字) = m(数据位) + r(冗余位)
• 码率（code rate）：m / n
• 海明距离（Hamming distance）：d = 一个码字要出现 d 个 1bit 的错误才会变成另一个码字。
  • 如果想可靠地 检测 可能的 e 个错误，需要海明距离为 e + 1 的编码方案
  • 如果想可靠地 纠正 可能的 e 个错误，需要海明距离为 2e + 1 的编码方案

纠错码

纠错码广泛运用于 无线链路。无线链路容易出错，如果没有纠错码很可能无法获得完全正确的信息。另外对于 单工信道 的情况，接收方如果检错到了错误也无法发回一个重发请求，也适用于纠错码。

• 海明码（Hamming codes）：需要每个码字都能纠正 1bit 的错误。对于 $2^m$ 种合法信息，每个信息都唯一对应 n 个非法码字，它们与合法信息的距离为 1。则共有 $2^m(n+1)$ 种情况，并满足 $2^m(n+1)\le 2^n$，即 $(m+r+1)\le 2^r$。

• 卷积码（convolutional codes）
• 里所罗门码（Reed-Solomon codes）
• 低密度奇偶校验码（Low-Density Parity Check）

检错码

光纤和高品质铜线的错误率较低，因此对偶现的错误进行检错和重传更加有效。

• 奇偶校验位（parity bit）
  • n-1 位信息，1 位冗余。奇校验码：在加上该位后 1 的个数为奇数；偶校验码则为偶数。
  • 交错校验 interleaving 技术可以一定程度上防止突发的若干比特范围内的错误。将数据块作为 k 行 n 列 处理，每列计算一个 parity bit 后附在数据块最后发送。这样除非突发错误持续 n 个 bit 以上，否则仍然可以被检测出来。
• 校验和（checksum）
  • 对数据进行一些求和运算。奇偶校验位也可以看做校验和的一个例子。
  • Internet Checksum：首先将数据分割成 16 bit 的若干段（最后一段不足 16 bit 则在末尾补 0）；然后将这些段相加，最高位进位 wrap around（加到第 0 位）。
• 循环冗余码（Cyclic Redundancy Code）
  • 
  • 假设除数的最高位为 r 阶，则为帧后面 添加 r 个 0
  • 使用“模二除法”的方式进行运算，每次与除数进行 异或
  • 最终得到的 余数为冗余码

流量控制 Flow Control

单工协议

• A Utopian Simplex Protocol
  • 发送方不断地从网络层获取数据包并构造成帧，通过物理层发送帧
  • 如果发送方发送帧的速度大于接收方处理的速度，接收方会被淹没（flood）
• A Simplex Stop-and-Wait Protocol for an Error-Free Channel
  • 接收方每当接收一个帧并处理完毕后，返回一个确认帧
  • 发送方在收到确认帧后，可以发送下一帧
  • 数据传输是 单工 的，但是需要使用 半双工信道
• A Simplex Stop-and Wait Protocol for a Noisy Channel
  • 接收到的帧发生错误：每次返回一个表示正确/错误的确认帧
  • 发送帧丢失：发送方设置计时器，若规定时间范围内没有收到确认帧，则重发
  • 防止重复收到帧：发送方发送第 i + 1 帧的充要条件是第 i 帧已经收到了正确的确认，可以维护奇偶性，以保证 不重复接收 帧

捎带确认 piggybacking

• 半双工信道和全双工信道都需要 两条信道，故最好用于往返传输数据。某一帧的接收方就可以把该帧的确认包含在它发回的另一帧的帧头中，这种方式就称为 捎带确认。
• 但捎带确认存在一个问题是：我们不知道网络层的下一次信息发送需求是什么时候，故需要设置一个计时器，当超时等待时，就发送一个单独的确认帧。

滑动窗口协议 Sliding Window Protocols

• 因为发出一帧的时间往往比通过信道中进行确认的时间开销少很多，这也导致带宽利用率较低，故引入滑动窗口协议。
• 滑动窗口允许维护一组允许发送帧的序号，并分为 发送窗口 和 接收窗口。
• 链路利用率
  • Line Utilization = Frame Length * 窗口数 / (Frame Length + 2 * Bandwidth * Propagation Delay)
  • Line Utilization = Frame Length * 窗口数 / (Frame Length + Bandwidth * Round-Trip Delay)
  • 当窗口数 $\ge 1+2\frac{T_{propagation}}{T_{transmision}}$ 时，链路利用率是 100%
  • 
• 链路吞吐率：Throughput = Utilization * Sending Data Rate
• 
• 回退 N 协议 GBN
  • 发送窗口大小：N
  • 接收窗口大小：1
  • 当发送的 N 个帧中，在位置 i 发生了错误，则 $[i,N-1]$ 的数据包都要重新发送
  • 
• 选择重传协议 SR
  • 当错误发生率较高时，使用 GBN 协议反而时间开销很大
  • 累计确认：当接收方发回 ACK n 的确认，其中表示 n 和 n 之前的所有帧都已经收到；如果 n 之前有任何没有收到的帧，则 ACK n 不会被发出。
  • 当接收方发现了发来的帧有错误或者不是所期待的那个帧时，发送一个否定的确认信息 NAK
  • 增大 receiving window size，这样当错误发生时可以先缓存一部分发来的后面的帧，这样发送方只需重发 NAK 的帧即可

点对点传输协议

高级数据链路控制 HDLC

• High-Level Data Link Control，一种传输可靠性高的协议

• Flag 采取 01111110；同时每连续 5 个 1，发送时就在后面添加一个 0
• Control 的前两位区分帧的用处
  • Informantion frame(0x)：信息帧，承载正常信息
  • Supervisory frame(10)：管理帧，用于流量控制和差错控制（如单独 ACK / NAK）
  • Un-numbered frame(11)：无编号帧，用于其他用途（如链路管理等）

点对点协议 PPP

• Point-to-Point Protocol，一种无连接无确认的协议
• Flag 采取 01111110；但是填充方式采用 byte stuffing：在数据中发现的 0x7E 将被替换为 0x7D 0x5E 两个字节；而 0x7D 将被替换为 0x7D 0x5D。
• 只支持 全双工 链路
• 两端可以运行 不同的网络层协议
• 提供 差错检测 但不提供纠错功能

广播信道传输协议

ALOHA, Additive Links On-line Hawaii Area

ALOHA 在传输帧的时候，不会侦听 信道是否繁忙（区分于 CSMA）；当发生碰撞（collision）时，冲突的信号源会选择等待一个随机长的时间再发送。

• Pure ALOHA：时间轴是连续的。
  • 其信道最高利用率为 18.4%
• Slotted ALOHA：时间轴是离散的。
  • 其信道最高利用率为 36.8%

载波侦听多路访问 CSMA, Carrier Sense Multiple Acess

CSMA 在传输帧的时候，会 侦听信道 是否繁忙，但不同的种类有不同的监听策略。在此协议中，若存在冲突检测（CSMA/CD），则应该将一个站的发送时间间隔至少设置为 $2t$ （假设两个最远的站传输所需时间为 $t$），若传输间隔小于该值，则无法确定出错的帧是哪一个。

• 1-persistent CSMA
  • 不断侦听信道，等到空闲就发送
  • 如果发送后发生冲突，就等待随机长的一段时间
• nonpersistent CSMA
  • 如果侦听到信道忙，则随机等待一段时间后再侦听
• p-persistent CSMA：
  • 将时间轴离散化
  • 如果侦听信道忙，则下一个 slot 再侦听
  • 如果侦听信道空闲，则以 $p$ 的概率发送，$1-p$ 的概率到下一个 slot 再侦听

载波侦听多路访问/碰撞检测 CSMA/CD, Carrier Sense Multiple Access with Collision Detection

• 以太网是无连接的，也并不提供确认，使用 1-persistent CSMA/CD 算法进行传输；它通过侦听有没有冲突来判断是否发送成功。如果站侦听到了冲突，则发一个短的冲突加强信号 (short jam signal) 确保另一个发送站也听到了冲突；如果没有侦听到冲突则假设这个帧发送成功。传输过程中发生的错误只会通过校验和检出并由高层负责恢复。
• 以太网通过 二进制指数后退（binary exponential backoff）算法确定每次冲突后的等待时间。
  • 回退算法
    • 将时间按照 51.2μs 分块
    • 在第 i = 1 ~ 9 次冲突发生后，等待 $0\sim (2^i-1)$ 个时间槽后再次尝试发送
    • 在第 i = 10 ~ 15 次冲突发生后，等待 $0\sim 1023$ 个时间槽后再次尝试发送
    • 在发生第 16 次冲突后，它放弃发送并给上层返回一个失败报告；高层协议负责进一步的恢复工作。
  • 作用：可以降低冲突发生的可能性；同时可以减少无意义的延迟。
• 最小帧长
  • 为保证在发送数据的过程中监测是否发生冲突（自己是否已经独占信道），需要保证发送的帧足够长。
  • 最小帧长 = 总线传播时延 × 数据传输速率 × 2

载波侦听多路访问/碰撞避免 CSMA/CA, Carrier Sense Multiple Access with Collision Avoidance

• CSMA/CA（CSMA with Collision Avoidance），不同于 CSMA/CD（CSMA with Collision Dectection），由于无线信道的半双工特性，我们只能尽可能地避免冲突的发生，而难以监测是否真正发生冲突。
• 算法
  • 侦听：在第一次发送前侦听一段时间（called DIFS），由此时间进行 倒计时，若倒计时期间又检测到有信息被发送，则等待，随后 继续 倒计时。
  • 确认：在接收端接收所有信息之后，发送一个 确认帧（ACK）。若发送端未接收到确认帧，则表明传输过程中出现了冲突或其他情况。
  • 侦听冲突：若在侦听时发生冲突，则选取一个随机回退值。一旦检测到信道忙，退避计时器就保持不变；只要信道空闲，退避计时器就进入倒计时。
  • 继续发送：若后续要继续发送帧，则随机选取一个时间进行侦听并发送。
  • 发送冲突（超时）：若发送站在规定时间内没有收到 确认帧，则认定为发送失败，进入侦听模式。
  • 

flowchart LR
	A((A发送消息))--->B(B接受消息)---C
	C((C接受消息))--->B---A
	A-.-|无法发现冲突|C

flowchart LR
	D---A((A发送消息))-.-|发现冲突|C((C发送消息))-->B(B接收消息)
	A-->D(D接收消息)
	B---C

无冲突协议 collision-free protocols

• 令牌环协议 Token Ring Protocol
  • 算法
    • 网络空闲时，环路中只有令牌帧在传递
    • 令牌传递到有数据要发送的站点时，就改变令牌的标志位，并附上自己要发送的数据，把令牌帧编程数据帧
    • 数据帧沿环路传输，到达目的站点时数据将被复制
    • 源站点收到发出去的帧后，检查是否发送出错，并 交出控制权 给下一个站点
  • 适用于 高负载、高冲突 的广播信道
• 基本位图协议 Basic Bit-map Protocol
  • 信号源发送数据前将请求提交给总站点
  • 总站点使用一个 位图 存储该时间段有哪些信号源要发送数据
  • 允许序号最小的信号源发送数据
• 二进制倒数协议 Binary CountDown Protocol
  • 每个要发送数据的信号源用二进制数表示，从高位到低位比较，如果当前位有数字是 1，则当前数字为 0 的信号源需等待，以此类推
  • 最后一定会找到一个唯一允许发送的信号源

有限竞争协议 limited-contention protocols

• 自适应树遍历协议 The Adaptive Tree Walk Protocol

局域网

• 常见局域网拓扑结构
  • 星形结构
  • 环形结构 → 令牌环
  • 总线形结构 → CSMA/CD 或 令牌总线
  • 星形和总线形复合型结构

以太网 Ethernet

• 以太网使用两种措施简化通信
  • 采用 无连接 的工作方式，不对发送的数据帧编号，也不要求接收方发送确认
  • 发送的数据均使用 曼彻斯特编码

WLAN

WLAN：Wireless LAN，作为无线通信系统，相比有线传输系统有更多需要克服的问题，如传输范围限制、冲突检测等等。

VLAN

• VLAN 期望将 物理拓扑 和 逻辑拓扑 分开，以提高网络的灵活性和安全性。

• 一个 VLAN 的示例如下图所示：将节点进行 染色区分，这样每个端口都会对应一种颜色（但如果端口对应的是另一个路由，则端口可能对应多种颜色）。在数据传输时，就可以通过网桥对包转发给 包含此颜色 的端口（这也要求 集线器 只能连接 相同颜色 的节点）。
  • 
• 为保证其通用性——能够和非 VLAN 网络兼容，路径中 第一个 VLAN-aware 的设备会负责 添加 VLAN 的字段，而 最后一个 VLAN-aware 的设备会将这额外的字段 删除。

广域网

• 广域网由一些结点交换机及连接这些交换机的链路组成
  • 结点交换机 的功能是将分组存储并转发
• 广域网在 OSI 参考模型中涉及物理层、数据链路层和网络层
• 连接广域网各节点的链路都是高速链路
  • 高速光缆
  • 点对点卫星链路
• 常见的两种广域网数据链路层协议为 PPP 协议和 HDLC 协议，均为点对点传输协议。

网桥 Network bridge

网桥是一种网络设备，负责网络桥接（network bridging）。桥接器将网络的多个网段在数据链路层连接起来（即桥接）。

• 工作原理
  • 维护一个哈希表，存储每个站点连接的是哪个端口。
    • 后向学习法
      • 将接收到的包中的信息（发送方 MAC 地址）和接收包的端口建立对应，更新哈希表。
      • 如果目标地址还不在哈希表中，则进行 泛洪（flooding），将包 转发给其他所有端口。
  • 接收所有的端口发送来的数据，若目标地址的端口和发送方对应的端口一致，则丢弃该包；否则将该包转发到目标地址对应端口中。

• 为了提高效率，我们也可以让网桥的每个接口独立地连接一个站点；上图展示了除了仍有一个 集线器（Hub）以外其他的站点都直接连接在了网桥上。对于每个端口，如果它连接的是全双工的点到点链路，那么它就不再需要 CSMA/CD 等冲突处理算法，因为它不会发生冲突。
• 因为支持多个端口并行传输，每个连接交换机的设备都能 占满总带宽

冗余链路 redundant links / parallel links

• 为提高可靠性，在网桥之间可建立冗余链路。
• 但冗余链路同时会造成 拓扑环路，导致数据在环路中循环传播而影响正常工作。
• 可使用 生成树算法，并 关闭 未被选择路径对应的 端口。